﻿#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"

//前序遍历-（根-左-右）
void qian(BT* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->arr);
	//左子树
	qian(root->zuo);
	//右子树
	qian(root->you);
}


//中序遍历-（左-根-右）
void zho(BT* root)
{
	if (root == NULL)
	{
		return;
	}
	//左子树
	zho(root->zuo);
	printf("%d ", root->arr);
	//右子树
	zho(root->you);
}


//后序遍历
void ho(BT* root)
{
	if (root == NULL)
	{
		return;
	}
	//左子树
	ho(root->zuo);
	//右子树
	ho(root->you);
	printf("%d ", root->arr);
}

// ⼆叉树结点个数 
int BinaryTreeSize(BT* root)
{
	if (root == NULL)
	{
		return 0;
	}
	//                左子树                     右子树
	return 1+ BinaryTreeSize(root->zuo)+ BinaryTreeSize(root->you);
}


// ⼆叉树叶⼦结点个数 
int BinaryTreeLeafSize(BT* root)
{
	if (root == NULL)
	{
		return 0;
	}
	//左子树和右子树都等于空，就是叶子节点
	if (BinaryTreeLeafSize(root->zuo) == NULL && BinaryTreeLeafSize(root->you) == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->zuo) + BinaryTreeLeafSize(root->you);
}


// ⼆叉树第k层结点个数 
int BinaryTreeLevelKSize(BT* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	//k等于1了就返回1
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->zuo, k - 1) + BinaryTreeLevelKSize(root->you, k - 1);
}




//⼆叉树的深度/⾼度
int BinaryTreeDepth(BT* root)
{
	if (root == NULL)
	{
		return 0;
	}
	//遍历左子树，把值给zuo
	int zuo = BinaryTreeDepth(root->zuo);
	//遍历右子树,把值给you
	int you = BinaryTreeDepth(root->you);
	//进行判断
	return zuo > you ? zuo + 1:you + 1;
}



// ⼆叉树查找值为x的结点 
BT* BinaryTreeFind(BT* root, data x)
{
	if (root == NULL)
	{
		return NULL;
	}
	//等于x，返回当前节点
	if (root->arr == x)
	{
		return root;
	}
	//zuo接收节点
	BT* zuo = BinaryTreeFind(root->zuo, x);
	if (zuo)
	{
		//返回节点
		return zuo;
	}
	//you接收节点
	BT* you = BinaryTreeFind(root->you, x);
	if (you)
	{
		//返回节点
		return you;
	}
}

// ⼆叉树销毁
void BinaryTreeDestory(BT** root)
{
	if (*root == NULL)
	{
		return;
	}
	//二级指针，需要传一级指针地址
	BinaryTreeDestory(&(*root)->zuo);
	BinaryTreeDestory(&(*root)->you);
	//释放空间
	free(*root);
	*root = NULL;
}

